package basic.study.wantOffer.chapter3;

/**
 * @author Kevin
 * @date 2020/5/3 11:02
 * 打印出1到n最大的n位数
 */
public class Problem17 {
    //方法1：模拟加一的方法
    public void print1ToMaxOfDigits(int n) {
        if (n <= 0) {
            return;
        }
        char[] number = new char[n];
        for (int k = 0; k < number.length; k++) {
            number[k] = '0';
        }
        while (!increment(number)) {
            printCharNumber(number);
        }
    }
    /**
     * 对字符串进行加一操作，number达到最大值后返回true
     * 最低位加一；所有位如果超过10，则进位
     */
    private boolean increment(char[] number) {
        int nTakeOver = 0;//代表进位
        for (int i = number.length -1; i >= 0; i--) {
            int nSum = (number[i] - '0') + nTakeOver;//当前位置数字
            if (i == number.length -1) {
                nSum++;
            }
            if (nSum >= 10) {
                if (i == 0) {
                    return true;//超出范围了
                }
                nTakeOver = 1;
                nSum -= 10;
                number[i] = (char)(nSum + '0');
            } else {
                number[i] = (char)(nSum + '0');
                break;//高位不变，可以直接跳出循环了
            }
        }
        return false;
    }
    /**
     * 打印字符数组形成的数字
     * 书中方法：利用布尔变量isBeginning0来从第一个非零字符打印
     */
    private void printCharNumber(char[] number) {
        boolean isBrginning0 = true;
        for (int i = 0; i < number.length; i++) {
            if (isBrginning0 && (number[i] - '0') != 0) {
                isBrginning0 = false;
            }
            if (!isBrginning0) {
                System.out.println(number[i]);
            }
        }
        System.out.println();
    }

    //=========方法二============
    /**
     * 采用递归的方法
     */
    public void print1ToMaxOfNDigits2(int n) {
        if (n <= 0)
            return;
        char[] number = new char[n];
        for (int k = 0; k < number.length; k++)
            number[k] = '0';
        for (int i = 0; i <= 9; i++) {
            makeNumber(n, number, i, 0);
        }
    }

    /**
     * 生成数字
     */
    private void makeNumber(int n, char[] number, int nNumber, int index) {
        if (index == number.length - 1) {
            number[index] = (char) (nNumber + '0');
            printCharNumber(number); // 打印数字代码与第一个方法一样
            return;
        } else {
            number[index] = (char) (nNumber + '0');
            for (int i = 0; i <= 9; i++) {
                makeNumber(n, number, i, index + 1);
            }
        }
    }
}
